import random


def linear_search(arr, target):
    """
    线性查找
    :param arr:
    :param target:
    :return:
    """
    for ind, val in enumerate(arr):
        if val == target:
            return ind
    else:
        return -1


def binary_search(arr, target):
    """
    二分查找 arr必须是有序的
    :param arr:
    :param target:
    :return:
    """
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if target == arr[mid]:
            return mid
        elif target < arr[mid]:
            high = mid - 1
        elif target > arr[mid]:
            low = mid + 1
    else:
        return -1


def bubble_sort(arr):
    """
    冒泡排序
    :param arr:
    :return:
    """
    for i in range(len(arr) - 1):
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


def bubble_sort_exchange(arr):
    """
    冒泡排序2
    :param arr:
    :return:
    """
    for i in range(len(arr) - 1):
        exchange = False
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                exchange = True
        if not exchange:
            break


def select_sort(arr):
    """
    选择排序
    每次找出一个最小的数
    :param arr:
    :return:
    """
    for i in range(len(arr) - 1):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
        if min_index != i:
            arr[min_index], arr[i] = arr[i], arr[min_index]


def insert_sort(arr):
    """
    插入排序
    :param arr:
    :return:
    """
    for i in range(1, len(arr)):
        sort_max_index = i - 1  # 有序区最大下标
        tmp = arr[i]  # 要插入的数
        while sort_max_index >= 0 and arr[sort_max_index] > tmp:  # max>=0 且 当前有序位置的数>要插入的数
            arr[sort_max_index + 1] = arr[sort_max_index]  # 挪位，腾出一个位置，扩充有序区
            sort_max_index -= 1  # 有序区的上一个索引
        arr[sort_max_index + 1] = tmp


def quick_sort(arr):
    """
    快速排序，暴力版，创建新的列表
    :param arr:
    :return:
    """
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left_list = [x for x in arr if x < pivot]
    center_list = [x for x in arr if x == pivot]
    right_list = [x for x in arr if x > pivot]
    return quick_sort(left_list) + center_list + quick_sort(right_list)


def partition(arr, low, high):
    # 选定第一个是基准
    pivot = arr[low]
    while low < high:
        # 从右边找比pivot小的数
        while low < high and arr[high] > pivot:
            high -= 1  # 右边索引减1，找下一个位置
        # 小于pivot的数填上 位置low
        arr[low] = arr[high]

        # 从左边找比pivot大的数
        while low < high and arr[low] <= pivot:
            low += 1  # 左边索引加1，找下一个位置
        # 大于pivot的数填上 位置high
        arr[high] = arr[low]

    # low == high 基准数归位
    # print(low == high, low, high)
    arr[low] = pivot

    return low


def quick_sort_2(arr, low, high):
    """
    快速排序，原地排序
    :param arr:
    :param low:
    :param high:
    :return:
    """
    if low < high:
        mid = partition(arr, low, high)
        quick_sort_2(arr, low, mid - 1)
        quick_sort_2(arr, mid + 1, high)
    return arr


a1 = [1, 3, 5, 6, 7, 9, 10]
print(linear_search(a1, 7))
print(binary_search(a1, 8))

a2 = [random.randint(1, 20) for _ in range(10)]
print(f"a2 before: {a2}")
bubble_sort(a2)
print(f"a2 after: {a2}")

a3 = [random.randint(1, 20) for _ in range(10)]
print(f"a3 before: {a3}")
bubble_sort_exchange(a3)
print(f"a3 after: {a3}")

a4 = [random.randint(1, 20) for _ in range(10)]
print(f"a4 before: {a4}")
select_sort(a4)
print(f"a4 after: {a4}")

a5 = [random.randint(1, 20) for _ in range(10)]
print(f"a5 before: {a5}")
insert_sort(a5)
print(f"a5 after: {a5}")

a6 = [random.randint(1, 20) for _ in range(10)]
print(f"a6: {a6}")
result = quick_sort(a6)
print(f"result: {result}")

a7 = [random.randint(1, 20) for _ in range(10)]
print(f"a7 before: {a7}")
quick_sort_2(a7, 0, len(a7) - 1)
print(f"a7 after: {a7}")
